Polish National Science Centre (NCN) grant 2014/15/B/ST6/00615
Compression, logic, formal languages: new approaches unifying different areas

07.2015–12.2018, this project has ended

Project focus

The main goal of the project is to apply recently developed technique of recompression to various fields of computer science. The technique itself is based on applying compression to implicit representation of strings and trees (like: grammars, solutions of equations etc.) and modifying those representations so that such compressions can be indeed applied. We would like to investigate topics related to context unification, word equations, grammars, etc.

For more information about the project, see its abstract or full description or contact project principal investigator, Artur Jeż.

Investigators

• Artur Jeż (principal investigator)
• Marek Szykuła (investigator)
• Sebastian Bala (investigator)
• Michał Gańczorz (investigator— MSc then PhD student)
• Robert Ferens (investigator—MSc student)

Publications

• A. Jeż Deciding Context Unification accepted to: Journal of the ACM
• M. Gańczorz, P. Gawrychowski, A. Jeż, T. Kociumaka Edit Distance with Block Operations ESA 2018 [conference version]
• J. Brzozowski, M. Szykuła Syntactic complexity of suffix-free languages Information and Computation, 259:174–190, 2018. [arXiv]
• M. Szykuła, J. Wittnebel Syntactic Complexity of Bifix-Free Languages. CIAA 2017, volume 10329 of LNCS, pages 201–212 full version: Syntactic complexity of bifix-free regular languages accepted to: Theoretical Computer Science [arXiv]
• A. Ryzhikov, M. Szykuła Finding Short Synchronizing Words for Prefix Codes MFCS 2018, volume 117 of LIPIcs, pages 21:1–21:14 [arXiv]
• M. Berlinkov, R. Ferens, M. Szykuła Complexity of Preimage Problems for Deterministic Finite Automata MFCS 2018, volume 117 of LIPIcs, pages 32:1–32:14 [arXiv]
• J. Brzozowski, L. Kari, Bai Li, M. Szykuła State Complexity of Overlap Assembly CIAA 2018, volume 10977 of LNCS, pages 109–120 [arXiv]
• B. Dudek, P. Gawrychowski Slowing Down Top Trees for Better Worst-Case Compression CPM 2018 [conference version]
• A. Jeż Word Equations in Nondeterministic Linear Space ICALP (B) 2017 [conference version, arXiv, presentation, long and technical presentation]
• M. Dżyga, R. Ferens, V. Gusev, M. Szykuła Attainable Values of Reset Thresholds MFCS 2017, volume 83 of LIPIcs, pages 40:1–40:14 [conference version]
• M. Gańczorz, A. Jeż Improvements on Re-Pair Grammar Compressor. DCC 2017
• A. Jeż, A. Okhotin Unambiguous Conjunctive Grammars over a One-Letter Alphabet Theoretical Computer Science 665: 13–39 (2017)
• M. Ganardi, D. Hucke, A. Jeż, M. Lohrey, E. Noeth Constructing small tree grammars and small circuits for formulas Journal of Computer Systems and Sciences 86: 136-158 (2017). [.pdf]
• P. Gawrychowski, A. Jeż LZ77 Factorisation of Trees. FSTTCS 2016 35:1-35:15 [conference version]
• J. Brzozowski, M. Szykuła Complexity of suffix-free regular languages Journal of Computer and System Sciences, 89:270–287, 2017 [arXiv]
• R. Ferens, M. Szykuła Complexity of Bifix-Free Regular Languages CIAA 2017, volume 10329 of LNCS, pages 76–88, 2017. full version accepted to: Theoretical Computer Science [arXiv]
• J. Brzozowski, Galina Jirásková, Bo Liu, and Aayush Rajasekaran, M. Szykuła On the State Complexity of the Shuffle of Regular Languages DCFS 2016, volume 9777 of LNCS, pages 73–86. [arXiv]
• V. Diekert, A. Jeż, W. Plandowski Finding All Solutions of Equations in Free Groups and Monoids with Involution Information and Computation [arXiv]
• M. Szykuła, M. Berlinkov Algebraic synchronization criterion and computing reset words Information Sciences, 369:718–730, 2016. [arXiv]
• A. Jeż, M. Lohrey Approximation of smallest linear tree grammar Information and Computation [arXiv]